1007. 行相等的最少多米诺旋转【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

在一排多米诺骨牌中，tops[i] 和 bottoms[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。）

我们可以旋转第 i 张多米诺，使得 tops[i] 和 bottoms[i] 的值交换。

返回能使 tops 中所有值或者 bottoms 中所有值都相同的最小旋转次数。

如果无法做到，返回 -1.

---

示例 1：

输入：tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
输出：2
解释：
图一表示：在我们旋转之前， tops 和 bottoms 给出的多米诺牌。
如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。

示例 2：

输入：tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]
输出：-1
解释：在这种情况下，不可能旋转多米诺牌使一行的值相等。

---

提示：

• 2 <= tops.length <= 2 * 10^4
• bottoms.length == tops.length
• 1 <= tops[i], bottoms[i] <= 6

2. 🎯 s.1 - 贪心

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} tops
 * @param {number[]} bottoms
 * @return {number}
 */
var minDominoRotations = function (tops, bottoms) {
  const n = tops.length
  const check = (target) => {
    let rotTop = 0
    let rotBot = 0
    for (let i = 0; i < n; i++) {
      if (tops[i] !== target && bottoms[i] !== target) return Infinity
      if (tops[i] !== target) rotTop++
      if (bottoms[i] !== target) rotBot++
    }
    return Math.min(rotTop, rotBot)
  }
  const res = Math.min(check(tops[0]), check(bottoms[0]))
  return res === Infinity ? -1 : res
}

• 时间复杂度：$O(n)$，其中 $n$ 是多米诺骨牌的数量
• 空间复杂度：$O(1)$，只使用了常数级别的额外空间

算法思路：

• 如果存在答案，目标值必然是 tops[0] 或 bottoms[0] 之一
• 对于一个目标值 target，遍历所有多米诺：
  • 如果某个多米诺两面都不含 target，则不可行
  • 否则分别统计把 target 放到上面和下面各需多少次旋转，取较小值